#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 最长子序列的个数：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
using namespace std;
class Solution {
public:
    //len[i]: 以i结尾的所有递增子序列中的最长长度
    //count[i]: 以i结尾的所有递增子序列中最长长度出现的次数
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> len(n,1);
        vector<int> count(n,1);
        int maxlen=1,maxcount=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])
                {
                    if(len[i]==len[j]+1) 
                        count[i]+=count[j];
                    else if(len[i]<len[j]+1)
                    {
                        len[i]=len[j]+1;
                        count[i]=count[j];
                    }
                }
            }
            if(maxlen<len[i])
            {
                maxlen=len[i];
                maxcount=count[i];
            }
            else if(maxlen==len[i])
            {
                //想想为什么是+=？ 其实很简单，已经知道了i位置的个数，
                //我要的是总个数，当然直接加起来
                maxcount+=count[i];
            }
        }
        return maxcount;
    }
};